package com.leo.datastruct.sort;

/**
 * 希尔排序 = 直接插入排序+gap分割
 * @author xuexiaolei
 * @version 2018年02月02日
 */
public class ShellSort extends Sortable {

    public ShellSort(String sortMethodName) {
        super(sortMethodName);
    }


    @Override public void sort(int[] s) {
        int gap = s.length/2;
        while (gap >= 1){
            for (int i = gap; i < s.length; i++) {
                int temp = s[i];
                int j = i;
                while (j-gap >= 0 && s[j-gap] > temp){
                    s[j] = s[j-gap];
                    j = j-gap;
                }
                s[j] = temp;
            }
            gap/=2;
        }
    }

    public static void main(String[] args) {
        Sortable a = new ShellSort("希尔排序");
        a.testSort(new int[]{49,38,65,97,76,13,27,49,78,34,12,64,1});
    }
}
